/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package practice.v2;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:ShellSort.java v1.0 2018/8/15 上午11:01 LvJing Exp $
 */
public class ShellSort {

    /**
     * 希尔排序：也是插入类型排序，第一趟先保证一定间隔的数组是有序的，保证有序方法为直接插入排序；第二趟间隔减半，重新保证有序。。。直到间隔
     * 减为1
     */
    public void shellSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1)
            return;

        int length = arr.length;
        for (int space = length/2; space > 0; space /= 2) {
            // 内部依然为直接插入排序
            for (int i = space; i < length; i++) {
                int temp = arr[i];
                int j;
                for (j = i; j > 0 && arr[j - 1] > temp; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[j] = temp;
            }
        }
    }

    @Test
    public void test01() {
        Random random = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++)
            arr[i] = random.nextInt(100);
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
